Classical worst-case optimization theory neither explains the success of optimization in machine learning, nor does it help with step size selection. In this paper we demonstrate the viability and advantages of replacing the classical'convex function' framework with a'random function' framework. With complexity \mathcal{O}(n 3d 3), where n is the number of steps and d the number of dimensions, Bayesian optimization with gradients has not been viable in large dimension so far. Specifically, we use a'stochastic Taylor approximation' to rediscover gradient descent, which is scalable in high dimension due to \mathcal{O}(nd) complexity. This rediscovery yields a specific step size schedule we call Random Function Descent (RFD).

While gradient based methods are ubiquitous in machine learning, selecting the right step size often requires "hyperparameter tuning". This is because backtracking procedures like Armijo's rule depend on quality evaluations in every step, which are not available in a stochastic context. Since optimization schemes can be motivated using Taylor approximations, we replace the Taylor approximation with the conditional expectation (the best $L^2$ estimator) and propose "Random Function Descent" (RFD). Under light assumptions common in Bayesian optimization, we prove that RFD is identical to gradient descent, but with calculable step sizes, even in a stochastic context. We beat untuned Adam in synthetic benchmarks. To close the performance gap to tuned Adam, we propose a heuristic extension competitive with tuned Adam.